题解

我们可以把第i层跟第i+1层之间楼梯的通断性构造成一个2*2的通断性矩阵，1表示通，0表示不通。那么从第a层到第b层，就是将a到b-1的通断性矩阵连乘起来，然后将得到的答案矩阵上的每个元素加起来即为方案数。想到矩阵的乘法是满足结合律的，那么我们可以用线段树来维护矩阵的乘积。每次我们只会修改某一个楼梯的通断性，所以就只是简单的线段树单点更新，成段求乘积而已。

图示

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <math.h>
#include <algorithm>
#define inf 0x3f3f3f3f
#define ll long long
#define mod 100000007
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int NV = 100005;
//int sum[NV<<2];
struct Matrix{
     ll v[3][3];
     Matrix  operator * (const Matrix & b)const{
        Matrix tt;
        for(int i=1;i<=2;i++){
            for(int j=1;j<=2;j++){
                tt.v[i][j]=(v[i][1] * b.v[1][j] % mod+ v[i][2] * b.v[2][j] % mod)%mod;
            }
        }
        return tt;
     }
}sum[NV<<2];
void PushUp(int rt)
{
    sum[rt]=sum[rt<<1]*sum[rt<<1|1];
}
void build(int l,int r,int rt=1)
{
    if (l == r)
    {
        sum[rt].v[1][1]=1;sum[rt].v[1][2]=1;
        sum[rt].v[2][1]=1;sum[rt].v[2][2]=1;
        return ;
    }
    int m = (l + r) >> 1;
    build(lson);
    build(rson);
    PushUp(rt);
}
void update(int L,int l,int r,int rt,int a,int b)
{
    if (L == l && l == r)
    {
        sum[rt].v[a][b] ^= 1;
        return ;
    }
    int m = (l + r) >> 1;
    if (L <= m) update(L  , lson,a,b);
    else update(L  , rson,a,b);
    PushUp(rt);
}
Matrix query(int L,int R,int l,int r,int rt=1)
{
    if (L <= l && r <= R)
        return sum[rt];
    int m = (l + r) >> 1;
    Matrix ret ;
    ret.v[1][1]=ret.v[2][2]=1;
    ret.v[1][2]=ret.v[2][1]=0;
    if (L <= m) ret =ret * query(L , R , lson);
    if (m < R) ret =ret * query(L , R , rson);
    return ret;
}
int m,n;
int main()
{
    while(~scanf("%d%d",&n,&m)){
        build(1,n);
        while(m--){
            int op;
            scanf("%d",&op);
            if(op){
                int x,d1,d2;
                scanf("%d%d%d",&x,&d1,&d2);
                update(x,1,n,1,d1,d2);
            }
            else{
                int d,u;Matrix tt;
                scanf("%d%d",&d,&u);
                tt=query(d,u-1,1,n);
                ll ans=0;
                for(int i=1;i<=2;i++)
                    for(int j=1;j<=2;j++){
                        ans=(ans+tt.v[i][j])%mod;
                    }
                printf("%I64d\n",ans);
            }
        }
    }
    return 0;
}